# candidates=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
# target=27
candidates=[10,1,2,7,6,1,5]
target=8
def combinationSum2(candidates,target):
    #深度优先遍历
    def dfs(begin,path,residue):
        #初始的residue为target值
        #递归出口
        if residue==0:
            #表示当前路径正好可以是一条可以得到结果的路径
            res.append(path[:])
            return None
        #递归循环，一个开始点，一个尺寸值
        for index in range(begin,size):
            if candidates[index]>residue:
                break
            if index>begin and candidates[index-1]==candidates[index]:
                continue
            path.append(candidates[index])
            dfs(index+1,path,residue-candidates[index])
            path.pop()
    #主函数
    #待处理序列的尺寸
    size=len(candidates)
    #如果尺寸为0，就直接返回空
    if size==0:
        return []
    #对待处理序列进行排序
    candidates.sort()
    #结果矩阵
    res=[]
    #进行递归遍历
    dfs(0,[],target)
    return res
print(combinationSum2(candidates,target))